package 中等.贪心思想;

import 算法模板.快速选择;

import java.util.Arrays;

/**
 * 给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。
 * 在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/
 */
public class 最少移动次数使数组元素相等II_462 {

    public static void main(String[] args) {

        int[] nums = {1, 0, 0, 8, 6};
        System.out.println(minMoves2(nums));

    }

    /**
     * 对于数组中的 最大值 max 和最小值 min
     * 显然 当 target>max || target <min 时，移动数一定会变大，
     * 去除掉数组中的最大值，最小值，得到一个子数组，那么选择子
     * 数组中的任何一个数字一定是变小的，如此反复，就是取数组的
     * 中间值，
     * 这里可以贪心的找越来越小的移动数，是因为选择子数组中任意
     * 一个数字，对于外层的移动数是不变的
     * 如果数组为偶数，那么最后剩下两个中间值，取任意一个中间值
     *
     * @param nums
     * @return
     */
    public static int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int target = nums[nums.length / 2];
        int ans = 0;
        for (int num : nums) {
            ans += Math.abs(num - target);
        }
        return ans;
    }

    //  快速选择
    public int minMoves(int[] nums) {
        int target = new 快速选择().findKthLargest(nums, nums.length / 2 + 1);
        int ans = 0;
        for (int num : nums) {
            ans += Math.abs(num - target);
        }
        return ans;
    }

}
